Timing channels are a form of a so-called side channel. A side channel is created by a circuit element that leaks information unintentionally. Side channels can be exploited by adversaries to extract secret information or compromise the correct operation of high integrity components. For example, a side channel can be used to extract a secret encryption key or to affect the time in which a braking system in a car responds to the press of the brake pedal.
Modern embedded computing systems, e.g., medical devices, airplanes, and automobiles, increasingly rely upon embedded computing systems. Such systems often include a system-on-chip. A system-on-chip includes multiple cores, controllers or processors on integrated single microchip. The movement of information in such systems should be tightly controlled to ensure security goals. This is challenging because information can flow through timing channels, which are difficult to detect. In turn, hardware designs that are insusceptible to timing channels are difficult to provide because the designs can't be effectively tested for possible flaws that support timing channels.
Seminal work by Kemmerer [R. A. Kemmerer, “Shared resource matrix methodology: an approach to identifying storage and timing channels,” ACM Trans. Comput. Syst., pp. 256-277, 1983], described an informal shared-resource matrix to pin-point potential timing channels. Effective at higher computing abstractions, this technique becomes difficult to apply to embedded and application-specific designs.
A number of Ad-hoc approaches [M. Hu, “Reducing timing channels with fuzzy time,” in Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 8-20, 1991], [. C. Wray, “An analysis of covert timing channels,” in Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 2-7, 1991] focus on introducing random noise into a system to make extracting information stochastically difficult. These methods make a timing channel harder to exploit (lower signal-to-noise ratio), but fail to identify whether a channel is timing-based. In addition, previous work using GLIFT has shown that strict information flow isolation can be obtained in a shared bus [J. Oberg, et al., “Information flow isolation in I2C and USB,” in Proceedings of Design Automation Conference (DAC) 2011, pp. 254-259, 2011.], but the work provides no ability to relate information to timing.
Typical information flow tracking strategies target hardware description languages [X. Li et al, Caisson: a hardware description language for secure information flow,” in PLDI 2011, pp. 109-120, 20], [T. K. Tolstrup, Language-based Security for VHDL. PhD thesis, Informatics and Mathematical Modelling, Technical University of Denmark, DTU, 2007]. This can be effective to prevent timing channels from developing. However, these languages force a designer to rewrite code in a new language. This is especially cumbersome when already designed hardware modules need to be analyzed.
Mobile systems and point of sale systems are of particular interest for security against information flows, including timing flows. The uses of mobile devices for trusted and confidential information exchanges continue to accelerate. Point of sale merchant systems have also proved vulnerable. Information stored and exchanges in these systems can include identity and financial account information.
Mobile phones, including phones having near field communication (NFC) capabilities, incorporate chips that allow the phones to securely store confidential information. Systems that interact with mobile systems, such as point of sale systems, also have security domains. Various secure domains are typically required to safeguard the flow of sensitive information, and to ensure that only specific secure domains have access to the information. The Smart Card Alliance has set forth guidelines for security in mobile payment platforms in Publication No. CPMC-09001, May 2009. Timing channels can be used to circumvent many such safeguards.
There are two general classes of information flows: explicit and implicit. Explicit information flows result from two subsystems directly communicating. For example, an explicit flow occurs when a host and device on a bus directly exchange data. Implicit information flows are much more subtle. Implicit flows generally leak information through behavior. Typical implicit information flows show up in hardware in the form of timing, where information can be extracted from the latency of operations.
For example, it is known that that side channel timing attacks can be used to extract secret encryption keys from the latencies of caches and branch predictors, for example. Cache timing attacks can obtain the secret key by observing the time for hit and miss penalties of the cache. Branch predictor timing channels are exploited in a similar manner, when information is leaked through the latency of predicted and mis-predicted branches. It has also been recognized that the shared bus in modern systems is a source of concern. A so-called bus-contention channel has been recognized as permitting covert transmission of information through the traffic on a global bus. See, e.g., W.-M. Hu, “Reducing timing channels with fuzzy time,” Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 8-20, 1991.
Information flow tracking is a common method used in secure systems to ensure that secrecy and/or integrity of information is tightly controlled. Given a policy specifying the desired information flows, such as one requiring that secret information should not be observable by public objects, information flow tracking helps detect whether or not flows violating this policy are present.
In general, information flow tracking associates data with a label that specifies its security level and tracks how this label changes as the data flows through the system. A simple example system has two labels: public and secret. A policy for the example system specifies that any data labeled as secret (e.g., an encryption key) should not affect or flow to any data labeled as public (e.g., a malicious process). Information flow tracking can also be extended to more complex policies and labeling systems. Information flow tracking has been used in all levels of the computing hierarchy, including programming languages [A. Sabelfeld and A. C. Myers, “Language-based information-flow security,” IEEE Journal on Selected Areas in Communications, 2003], operating systems [M. Krohn, et al., “Information flow control for standard os abstractions,” in SOSP 2007, pp. 321-334, 2007.], and instruction-set/microarchitectures [G. E. Suh, et al., “Secure program execution via dynamic information flow tracking,” in ASPLOS 2004, pp. 85-96, 2004.], [J. R. Crandall et al., “Minos: Control data attack prevention orthogonal to memory model,” in MICRO 2004, pp. 221-232, 2004.]. Recently, information flow tracking was used by Tiwari et al. [M. Tiwari, et al., “Execution leases: a hardware-supported mechanism for enforcing strong non-interference,” in MICRO 2009, MICRO 42, pp. 493-504, 2009] at the level of logic gates in order to dynamically track the flows of each individual bit.
In the technique used by Tiwari et al., called gate level information flow tracking (GLIFT), the flow of information for individual bits is tracked as the bits propagate through Boolean gates; GLIFT was later used by Oberg et al. [J. Oberg, et al., “Information flow isolation in I2C and USB,” in Proceedings of Design Automation Conference (DAC) 2011, pp. 254-259, 2011.] to test for the absence of all information flows in the I2C and USB bus protocols and by Tiwari et al. [M. Tiwari, et al., “Complete information flow tracking from the gates up,” in Proceedings of ASPLOS 2009, 2009] to build a system that provably enforces strong non-interference. Further, it has been used to prove timing-based non-interference for a network-on-chip architecture in the research project SurfNoC [H. M. G. Wassel et al., “Surfnoc: a low latency and provably non-interfering approach to secure networks-on-chip.,” in ISCA, pp. 583-594, ACM, 2013.] Since its introduction, Tiwari et al. have expanded GLIFT to “star-logic,” which provides much stronger guarantees on information flow [M. Tiwari, et al., “Complete information flow tracking from the gates up,” in Proceedings of ASPLOS 2009, 2009]. Generally, GLIFT tracks flow through gates by associating with each data bit a one-bit label, commonly referred to as taint, and tracking this label using additional hardware known as tracking logic, which specifies how taint propagates.
Gate-level information flow tracking (GLIFT) provides the ability to test for information flows. See, e.g., Oberg et al., “Information Flow Isolation in I2C and USB,” DAC 2011, Jun. 5-10, 2011. Chip designers can test for information flows prior to fabricating a chip with GLIFT. However, GLIFT merely provides identification of information flows, and only with the single bit tag that is labeled taint. GLIFT tracks each individual bit in a system as the bits propagate through Boolean gates.
GLIFT can be applied, for example, after a design is synthesized into a gate-level netlist. With GLIFT, each gate is then associated with tracking logic. The function of the tracking logic depends on the function of the gate. The process is similar to a technology mapping, where each gate in the system is mapped to specific GLIFT logic. The result is a gate-level design of a finite state machine (FSM) that contains both the original logic and tracking logic. The resulting design equipped with tracking logic can be tested for information flows. To test for implicit timing flows, GLIFT accounts for all possible combinations of tainted data bits, and allows information flows to be observed. A designer can than make appropriate modifications to the chip design. Since GLIFT targets the lowest digital abstraction, it is able to detect and capture information leaking through time. However, GLIFT fails to provide any ability to separate timing information from functional information. Accordingly, a hardware designer using GLIFT would be unable to determine with a suspect flow is direct or indirect.
The Bus Covert Channel
Shared buses, such as the inter-integrated circuit (I2C) protocol, universal serial bus (USB), and ARM's system-on-chip AMBA bus, lie at the core of modern embedded applications. Buses and their protocols allow different hardware components to communicate with each other. For example, they are often used to configure functionality or offload work to co-processors (GPUs, DSPs, FPGAs, etc.). As the hardware in embedded systems continues to become more complex, so do the bus architectures themselves. The complexity makes it difficult to identify potential security weaknesses.
In terms of such security weaknesses, a global bus that connects high and low entities has inherent security problems. An example is a denial-of-service attack. In such an attack, a malicious device starves a higher integrity device from bus access. Another example is bus-snooping, in which a low device can learn information from a higher one. An inefficient and expensive solution that has been used to avoid these problems involves designers building physically isolated high and low buses.
The covert channels associated with common buses are well researched. One such channel, the bus-contention channel [W.-M. Hu, “Reducing timing channels with fuzzy time,” in Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 8-20, 1991.] arises when two devices on a shared bus communicate covertly by modulating the amount of observable traffic on the bus. For example, if a device A wishes to send information covertly to a device B, it can generate excessive traffic on the bus to transmit a 1 and minimal traffic to transmit a 0. Even if A is not permitted to directly exchange information with B, it still may transmit bits of information using this type of covert channel.
The two most well-known solutions to the bus-contention channel are clock fuzzing [W.-M. Hu, “Reducing timing channels with fuzzy time,” in Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 8-20, 1991.] and probabilisitic partitioning [ ] J. W. Gray III, “On introducing noise into the bus-contention channel,” in Proceedings of the 1993 IEEE Symposium on Security and Privacy, pp. 90-98, 1993.]. Clock fuzzing utilizes a skewed and seemingly random input clock. The fuzzy clock makes it stochastically difficult for two covert devices to synchronize. This technique has limited appeal because it reduces the bandwidth of the bus [ ] J. W. Gray III, “On introducing noise into the bus-contention channel,” in Proceedings of the 1993 IEEE Symposium on Security and Privacy, pp. 90-98, 1993.]. Probabilistic partioning permits devices to access the bus in isolated time slots in a round-robin fashion. Two modes are chosen at random: secure and insecure. In insecure mode, the bus operates in the standard fashion where devices contend for its usage. In secure mode, the bus is allocated to each device in a time-multiplexed round-robin manner. The contention phase burdens bandwidth also.
Cache Timing Channel
CPU caches in modern processors have been demonstrated to be highly susceptible to hardware timing channels [D. Gullasch, et al., “Cache games—bringing access-based cache attacks on AES to practice,” in Proceedings of the 2011 IEEE Symposium on Security and Privacy, pp. 490-505, 2011]. Caches are typically built from faster and higher power memory technologies, such as SRAM, and sit between slower main memory (typically DRAM) and the CPU core.
The non-deterministic latencies of caches are a direct source of timing channels. When a memory region is referenced that is currently stored in the cache (a cache hit), the time to receive the data is significantly faster than if it needs to be retrieved from main memory (a cache miss). Many data encryption algorithms, such as the advanced encryption standard (AES), use look-up tables based on the value of the secret key. Since a look-up table will return a value in an amount of time that is directly correlated with whether or not the value is already cached, observing the timing of interactions with the look-up table produces valuable information about the secret key.
This vulnerability has been previously demonstrated to permit complete extraction of the secret key via different attacks. The attacks include trace-driven [O. Aciiçmez et al., “Trace-driven cache attacks on AES (short paper),” in ICICS, pp. 112-121, 2006], time-driven [D. J. Bernstein, “Cache-timing attacks on AES.” Technical Report, 2005.], [D. A. Osvik, et al., “Cache attacks and countermeasures: the case of aes,” in Proceedings of the 2006 The Cryptographers' Track at the RSA conference on Topics in Cryptology, pp. 1-20, 2006.], and access-driven [D. Gullasch, et al. “Cache games—bringing access-based cache attacks on AES to practice,” in Proceedings of the 2011 IEEE Symposium on Security and Privacy, pp. 490-505, 2011]. Trace-driven attacks require an adversary to have detailed cache profiling information. The adversary therfore requires physical access or another wire to obtain fine granularity cache information. Time-driven attacks collect timing measurements over several encryptions by a remote server and correlate their running time to the value of the secret key. This type of attack has been shown capable of extracting a complete 128-bit AES key [D. J. Bernstein, “Cache-timing attacks on AES.” Technical Report, 2005.]. Access-driven attacks exploit knowledge about which cache lines are evicted. In particular, a malicious process observes the latency of cache misses and hits and uses these patterns to deduce which cache lines are brought in/evicted, which in turn leaks information about the memory address (e.g., the secret key in AES table look-ups). This type of cache attacks has applications beyond just encryption, such as on virtulized systems [T. Ristenpart, et al., “Hey, you, get off of my cloud! Exploring information leakage in third-party compute clouds,” in Proceedings of CCS 2009, pp. 199-212, 2009.].
Most previous work on timing channels has focused on techniques for identifying timing and storage channels in larger systems, but not specifically in hardware designs. Prior efforts have reduced or eliminated specific timing channels. Little work concerned systematic testing techniques for identifying such channels.
Wray [R. A. Kemmerer, “Shared resource matrix methodology: an approach to identifying storage and timing channels,” ACM Trans. Comput. Syst., pp. 256-277, 1983.] describes analysis of timing and storage channels in the VAX Virtual Machine Monitor. The timing channels are specific to the VAX VMM and a systematic testing method for identifying the channels is not described.
Kemmerer [R. A. Kemmerer, “Shared resource matrix methodology: an approach to identifying storage and timing channels,” ACM Trans. Comput. Syst., pp. 256-277, 1983.] presents a shared matrix methodology for identifying timing channels. A matrix is created that compares shared resources, processes, and resource attributes. Based on these fields and some proposed criteria for a timing and storage channel, the matrix can be analyzed to determine whether or not a shared resource can be used as a side channel. This technique therefore requires the designer to construct such a matrix and determine the shared resources, but ultimately still does not provide a general technique for detecting timing channels in hardware.
Clock fuzzing is a technique for timing channel mitigation in secure systems [W.-M. Hu, “Reducing timing channels with fuzzy time,” in Proceedings of the 1991 IEEE Symposium on Security and Privacy, pp. 8-20, 1991.]. Clock fuzzing works by presenting the system with a seemingly random clock to make it stochastically difficult for two objects to synchronize. Clock fuzzing is ineffective because it reduces the bandwidth of the timing channel and does not eliminate it entirely.
More recent work has focused on hardware information flow tracking. Dynamic information flow tracking (DIFT) [. E. Suh, et al., “Secure program execution via dynamic information flow tracking,” in ASPLOS 2004, pp. 85-96, 2004.] tags information that comes from potentially untrusted channels and tracks them throughout a processor. This tag is checked before branches in execution are taken, and the branch is prevented if this information originated from an untrusted source. As demonstrated by Suh et al., DIFT is quite effective at detecting buffer overflow and format-string attacks, but works at too high of an abstraction to track information through timing channels. A similar tracking system [J. R. Crandall et al., “Minos: Control data attack prevention orthogonal to memory model,” in MICRO 2004, pp. 221-232, 2004.] keeps an integrity bit on information and uses this bit to prevent potentially malicious branches in execution. Another example [M. Dalton, et al., “Raksha: a flexible information flow architecture for software security,” in ISCA 2007, pp. 482-493, 2007] is a DIFT style processor that allows security policies to be reconfigured. Others have described a hardware security language [X. Li, et al., “Caisson: a hardware description language for secure information flow,” in PLDI 2011, pp. 109-120, 2011.] that aids hardware designers by using programming language type-based techniques to prevent unintended information flows and eliminate timing channels.
Gate level information flow tracking (GLIFT) has been developed by the present inventors and colleagues. GLIFT [M. Tiwari, et al., “Execution leases: a hardware-supported mechanism for enforcing strong non-interference,” in MICRO 2009, MICRO 42, pp. 493-504, 2009] works by tracking each individual bit in a hardware system. It is a general technique that has been applied to build an execution lease CPU [M. Tiwari, et al., “Crafting a usable microkernel, processor, and I/O system with strict and provable information flow security,” in Proceedings of ISCA 2011, pp. 189-200, 2011.] and to analyze information flows in bus protocols [J. Oberg, et al., “Information flow isolation in I2C and USB,” in Proceedings of Design Automation Conference (DAC) 2011, pp. 254-259, 2011.]. Recently, information flow tracking has also been used in hardware design languages. This work is effective at helping hardware designers to build secure hardware, but fails to provide a general technique for testing for timing channels.